package recursion;

import java.util.Arrays;

/**
 * 迷宫回溯问题
 */
public class MiGong {
  public static void main(String[] args) {
    int[][] map=new int[8][7];
    Arrays.fill(map[0], 1);
    Arrays.fill(map[7], 1);
    for (int i = 0; i < map.length; i++) {
      map[i][0]=1;
      map[i][6]=1;
    }
    map[3][1]=1;
    map[3][2]=1;

    System.out.println("地图情况");
    for (int[] row : map) {
      for (int i : row) {
        System.out.print(i+"  ");
      }
      System.out.println();
    }
    findWay(map,1,1);
    System.out.println("地图情况");
    for (int[] row : map) {
      for (int i : row) {
        System.out.print(i+"  ");
      }
      System.out.println();
    }
  }

  /**
   *到达[6][5]，则找到终点
   * 为0表示未走过，1表示墙，2表示可以走，3表示走过且不可以走
   * 策略，先向下走，再右，再上，再左
   */
  public static boolean findWay(int[][] map,int i,int j){
    if (map[6][5]==2){//递归出口
      return true;
    }

    if (map[i][j]==0){//未走过
      map[i][j]=2;
      if (findWay(map,i+1,j)){
        return true;
      }else if (findWay(map,i,j+1)){
        return true;
      }else if (findWay(map,i-1,j)){
        return true;
      }else if (findWay(map,i,j-1)){
        return true;
      }else {
        map[i][j]=3;
        return false;
      }
    }else {//为1,2,3
      return false;
    }
  }
}
